package pers.tz.题目.leetcode.树;

/**
 * @author irony
 * @date 2024-03-12
 */
public class leetcode_0208_实现_Trie_前缀树 {
    public static void main(String[] args) {
        Trie obj = new Trie();
        obj.insert("app");
        obj.insert("apple");
        boolean param_2 = obj.search("apps");
//        System.out.println("param_2 = " + param_2);
        boolean param_3 = obj.search("app");
//        System.out.println("param_3 = " + param_3);
    }
}

class Trie {

    private Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String word) {
        if (word == null || word.isEmpty()) {
            return;
        }

        char[] charArray = word.toCharArray();
        root.pass++; // 记录
        int path = 0; // 路径
        Node cur = root;

        for (char c : charArray) {
            path = c - 'a';
            if (cur.next[path] == null) {
                cur.next[path] = new Node();
            } else {
                cur.next[path].pass++;
            }

            cur = cur.next[path];
        }
        cur.end++;
    }

    public boolean search(String word) {
        if (word == null || word.isEmpty()) {
            return false;
        }
        if (root == null) {
            return false;
        }

        char[] charArray = word.toCharArray();
        Node cur = root;
        int path = 0;
        for (char c : charArray) {
            path = c - 'a';
            if (cur.next[path] == null) {
                return false;
            }
            cur = cur.next[path];
        }

        return cur.end != 0;
    }

    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.isEmpty()) {
            return false;
        }

        char[] charArray = prefix.toCharArray();
        Node cur = root;
        int path = 0;
        for (char c : charArray) {
            path = c - 'a';
            if (cur.next[path] == null) {
                return false;
            }
            cur = cur.next[path];
        }

        return true;
    }
}

class Node {
    // 原题共pass是不需要的
    // 记录该节点经过了多少次，用于支持获取前缀数量O(M)，M是前缀中的字符数量
    int pass;

    // 记录该节点是多少字符串的结束位置，用于支持获取字符串数量O(M)
    int end;

    // 下级节点
    Node[] next;

    public Node() {
        this.pass = 0;
        this.end = 0;

        // 0 - a
        // 1 - b
        // 'a' - 'a' = 0
        // 'b' - 'a' = 1
        // char - 'a' = index
        this.next = new Node[26];
    }
}
